《算法设计与分析》引论

第一章

数据结构+算法

输入、输出、有穷、确定

正确性、可读性、健壮性、高效率和低存储量需求

复杂度按数量级递增排列依次为：常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O($n^{2}$)、立方阶O($n^{3}$)、…、k次方阶O($n^{k}$)、指数阶O($2^{n}$)、阶乘阶($n!$)。

Ω	O	θ	o
≥ 渐渐下界	≤ 渐进上界	＝	＜

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是？

1
2
3

x=2;
while(x<n)
	x = x+2;

A． $O(log_{2}n)$ B．O(n)
C． $O(nlog_{2}n)$ D． $O(n^{2})$

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是？

1
2
3

x=2;
while(x<n/2)
	x = 2*x;

答： $O(log_{2}n)$

解析：在程序中，执行频率最高的语句为”x = 2*x “。设该语句共执行了T (n)次，则 $2^{T(n)+1}<n/2$ ，故 $T(n)=O(log_{2}n)$

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是？

1
2
3

x=2;
while(x<n)
	x = x*x;

A． $O(log_{2}n)$ B． $O(n)$
C． $O(nlog_{2}n)$ D． $O(log_{2}log_{2}n)$

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。

void fun(int n){ 
	int i，k； 
	for(i＝1；i<＝n；i＋＋) 
		for(j＝1；j<＝n；j＋＋){ 
			k＝1： 
			while(k<＝n)
				k＝5*k； 
		} 
}

A．O($n^{2}\log{2}n$)
B．O($n\log{5}n$)
C．O($n^{2}\log_{5}n$)
D．O($n^{3} $)

答案：C。解析：基本运算语句是k＝5*k，设其执行时间为T(n)。对于j每循环一次，该语句的执行次数为m，有：$5^{m}$ ≤n，即m≤$\log_{5}n$。所以：

算法思考题：
一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如第6页用6表示而不是06或006。数字统计问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0,1,2,…,9。

思考：算法复杂度描述中为什么用“logn”，而不用“$\log_{2}n$”、“lnn”或“lgn”？

已知数组a[n]中，有且仅有两个元素值相等，其他元素各不相等。请找出相同的元素值？

对数组a[n]中值相等的元素，仅保留一个、其余去除，并紧凑排列？

去除有序数组a[n]中的重复元素。比如：1,1,2,2,2,3,3,3,4,5,6,6 → 1,2,3,4,5,6？

// 方法一
for(i=1; i<n; i++){
   if(a[i-1]==a[i]) 
        for(j=i; j<n; j++){
              a[j]=a[j+1];
        }
}

// 方法二
for(i=1; i<n; i++){
   j=i;
   while(a[i-1]==a[j] && j<n)  j++;   // 减少移动次数
   for(; j<n; j++){
       a[j]=a[j+1];
   }
}

// 方法三
i=0;
while(j<n){
   j=i+1;
   while(a[i]==a[j] && j<n) j++;   
   if(j<n) a[i++]=a[j];
}